{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Extra Characters in a String"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #trie #array #hash-table #string #dynamic-programming"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #字典树 #数组 #哈希表 #字符串 #动态规划"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: minExtraChar"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #字符串中的额外字符"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个下标从 <strong>0</strong>&nbsp;开始的字符串&nbsp;<code>s</code>&nbsp;和一个单词字典&nbsp;<code>dictionary</code>&nbsp;。你需要将&nbsp;<code>s</code>&nbsp;分割成若干个 <strong>互不重叠</strong>&nbsp;的子字符串，每个子字符串都在&nbsp;<code>dictionary</code>&nbsp;中出现过。<code>s</code>&nbsp;中可能会有一些&nbsp;<strong>额外的字符</strong>&nbsp;不在任何子字符串中。</p>\n",
    "\n",
    "<p>请你采取最优策略分割 <code>s</code>&nbsp;，使剩下的字符 <strong>最少</strong>&nbsp;。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre><b>输入：</b>s = \"leetscode\", dictionary = [\"leet\",\"code\",\"leetcode\"]\n",
    "<b>输出：</b>1\n",
    "<b>解释：</b>将 s 分成两个子字符串：下标从 0 到 3 的 \"leet\" 和下标从 5 到 8 的 \"code\" 。只有 1 个字符没有使用（下标为 4），所以我们返回 1 。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre><b>输入：</b>s = \"sayhelloworld\", dictionary = [\"hello\",\"world\"]\n",
    "<b>输出：</b>3\n",
    "<b>解释：</b>将 s 分成两个子字符串：下标从 3 到 7 的 \"hello\" 和下标从 8 到 12 的 \"world\" 。下标为 0 ，1 和 2 的字符没有使用，所以我们返回 3 。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= s.length &lt;= 50</code></li>\n",
    "\t<li><code>1 &lt;= dictionary.length &lt;= 50</code></li>\n",
    "\t<li><code>1 &lt;= dictionary[i].length &lt;= 50</code></li>\n",
    "\t<li><code>dictionary[i]</code>&nbsp;和&nbsp;<code>s</code>&nbsp;只包含小写英文字母。</li>\n",
    "\t<li><code>dictionary</code>&nbsp;中的单词互不相同。</li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [extra-characters-in-a-string](https://leetcode.cn/problems/extra-characters-in-a-string/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [extra-characters-in-a-string](https://leetcode.cn/problems/extra-characters-in-a-string/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['\"leetscode\"\\n[\"leet\",\"code\",\"leetcode\"]', '\"sayhelloworld\"\\n[\"hello\",\"world\"]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minExtraChar(self, s: str, dictionary: List[str]) -> int:\n",
    "        n, dictionary_set = len(s), set(dictionary)\n",
    "        @cache\n",
    "        def dp(start):\n",
    "            if start == n:\n",
    "                return 0\n",
    "            # To count this character as a left over character \n",
    "            # move to index 'start + 1'\n",
    "            ans = dp(start + 1) + 1\n",
    "            for end in range(start, n):\n",
    "                curr = s[start: end + 1]\n",
    "                if curr in dictionary_set:\n",
    "                    ans = min(ans, dp(end + 1))\n",
    "            return ans\n",
    "            \n",
    "        return dp(0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minExtraChar(self, s: str, dictionary: List[str]) -> int:\n",
    "        dic=set(dictionary)\n",
    "        A=set()\n",
    "        for i in dic:\n",
    "            A.add(len(i))\n",
    "        dp=[0]*(len(s)+1)\n",
    "        for i in range(1,len(s)+1):\n",
    "            m=dp[i-1]+1\n",
    "            for j in A:\n",
    "                if i-j>=0 and s[i-j:i]in dic:\n",
    "                    m=min(m,dp[i-j])\n",
    "            dp[i]=m\n",
    "        return dp[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minExtraChar(self, s: str, dictionary: List[str]) -> int:\n",
    "        d = set(dictionary)\n",
    "        n = len(s)\n",
    "        f = [0] * (n + 1)\n",
    "        for i in range(n):\n",
    "            f[i + 1] = f[i] + 1\n",
    "            for j in range(i + 1): \n",
    "                if s[j:i + 1] in d:\n",
    "                    f[i + 1] = min(f[i + 1], f[j])\n",
    "        return f[n]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minExtraChar(self, s: str, dictionary: List[str]) -> int:\n",
    "        #解题思路：\n",
    "        #对于以s[i]结尾的子串，有两个选择，选或不选\n",
    "        #选：dp[i] = dp[j],if [j:i+1] in dictionary\n",
    "        #不选：dp[i] = dp[i - 1] + 1\n",
    "\n",
    "        n = len(s)\n",
    "        d = set(dictionary)\n",
    "        dp = [0] * (n + 1)\n",
    "        \n",
    "        for i in range(1,n + 1):\n",
    "            dp[i] = dp[i - 1] + 1\n",
    "            for j in range(i):\n",
    "                if s[j:i] in d:\n",
    "                    dp[i] = min(dp[i],dp[j])\n",
    "        return dp[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minExtraChar(self, s: str, dictionary: List[str]) -> int:\n",
    "        dic = set(dictionary)\n",
    "        stend = []\n",
    "        # 感觉是你n^3的\n",
    "        for i in range(len(s)):\n",
    "            for j in range(i+1,len(s)+1):\n",
    "                sub = s[i:j]\n",
    "                if sub in dic:\n",
    "                    stend.append([i,j])\n",
    "        if len(stend) == 0:\n",
    "            return len(s)\n",
    "        # 变换成了一个组合的问题了\n",
    "        dp = [0]*len(stend)\n",
    "        # dp[i]为选择i个时候能够最大的值\n",
    "        dp[0] = stend[0][1] - stend[0][0]\n",
    "        for i in range(1,len(dp)):\n",
    "            istart = stend[i][0]\n",
    "            max_i = -inf \n",
    "            for index in range(i):\n",
    "                if stend[index][1] <= istart:\n",
    "                    max_i = max(max_i,dp[index])\n",
    "            dp[i] = max(max_i + stend[i][1]-stend[i][0],stend[i][1]-stend[i][0])\n",
    "        return len(s) - max(dp)\n",
    "        \n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minExtraChar(self, s: str, dictionary: List[str]) -> int:\n",
    "        n = len(s)\n",
    "        dictionary.sort(key = lambda x : len(x))\n",
    "        \n",
    "        @cache\n",
    "        def dfs(index):\n",
    "            #print(\"index -\", index)\n",
    "            if index == n:\n",
    "                return 0\n",
    "            ans = inf\n",
    "            for word in dictionary:\n",
    "                #print(word, len(word))\n",
    "                w_len = len(word)\n",
    "                if index + w_len > n:\n",
    "                    break\n",
    "                if word == s[index:index + w_len]:\n",
    "                    ans = min(ans, dfs(index + w_len))\n",
    "            ans = min(ans, 1 + dfs(index + 1))\n",
    "            return ans\n",
    "        \n",
    "        return dfs(0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minExtraChar(self, s: str, dictionary: List[str]) -> int:\n",
    "        trie = {}\n",
    "        for word in dictionary:\n",
    "            ptr = trie\n",
    "            for c in word:\n",
    "                if c not in ptr:\n",
    "                    ptr[c] = {}\n",
    "                ptr = ptr[c]\n",
    "            ptr[\"$\"] = 1\n",
    "        \n",
    "        n = len(s)\n",
    "        dp = [0] * (n + 1)\n",
    "        for i in range(n - 1, -1, -1):\n",
    "            ptr = trie\n",
    "            dp[i] = dp[i + 1] + 1\n",
    "            for j in range(i, n):\n",
    "                if s[j] not in ptr:\n",
    "                    break\n",
    "                ptr = ptr[s[j]]\n",
    "                if \"$\" in ptr and dp[i] > dp[j + 1]:\n",
    "                    dp[i] = dp[j + 1]\n",
    "\n",
    "        return dp[0]\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
